The present invention relates to the field of resolution conversions of digital data and in particular digital image data. The current invention is particularly advantageous for a resolution conversion implementation that uses samples from a continuous kernel as coefficients in the convolution operation. The current invention also provides an efficient software algorithm to implement resolution conversion.
A filter function used in digital data resolution conversion is often called a convolution kernel, a filter kernel or just a kernel. When a kernel produces data that passes through original data points of a sampled signal, it is often called an interpolating kernel and when the interpolated data produced is not constrained to pass through the original data points it is often called an approximating kernel.
Prior art kernels for digital data resolution conversion include the nearest neighbour (NN), linear, quadratic and cubic kernels. The NN kernel is the simplest method of interpolation, simply interpolating the image with the pixel value that is spatially nearest to the required pixel value. This method works quite well when the scaling ratio is an integer multiple of the original data as it introduces no new values, ie. no new colours, and preserves sharp edges. However, at other ratios the NN kernel has the disadvantage of shifting edge locations which often produces visible distortions in the output image, especially in images containing text or fine line details. Linear interpolation on the other hand allows for the introduction of new grey levels (or colours) that are effectively used to position edges at sub-pixel locations. This has the advantage of reducing the effect of shifted edge locations, however sharp edges can now appear to be blurred. Quadratic and cubic interpolation provide steeper step responses and therefore less edge blurring, however, the steeper response results in an overshoot on either side of the edge. These overshoots can make the edges in natural images appear sharper, but on text, fine lines, or on other computer generated graphics these overshoots are clearly visible and detract from the perceived image quality and text legibility.
Hardware to perform two dimensional image interpolation using a method of cubic convolution is known whereby pre-calculated values of the two-dimensional cubic convolution kernel are stored in a look-up table (LUT) and then simultaneously 16 (4xc3x974) coefficient values are read and multiplied with 16 pixels in the original image surrounding the pixel location to be interpolated. Storing the coefficient values in a look-up table removes the need to calculate the coefficients at each interpolated pixel and therefore increases the speed of execution of the algorithm.
Another technique performs two-dimensional interpolation by first interpolating the rows of an image and then interpolating the columns of the image. Up to 4 coefficients for each of the one-dimensional convolution kernels are again read from a LUT, multiplied with data, and summed to produce an interpolated pixel. However, this implementation, which is commonly referred to as a xe2x80x9cseparable implementationxe2x80x9d, is not as fast as the two-dimensional implementation discussed above, although significant reductions in the memory requirements of the LUT may be obtained.
There is a problem however, with both of these known methods in that pre-calculating values and storing them in a LUT introduces an error between the actual coefficient value required for the interpolation and the closest value stored in the LUT. Storing more values in the LUT can reduce this error, however, this can drastically increase the amount of storage required for the LUT.
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
One or more exemplary aspects of the invention are listed below, but are not limited thereto.
According to one aspect of the invention there is provided a method of converting a first set of discrete data values to a second set of discrete data values, the method comprising the following steps:
(i) calculating a scaling factor of said first set of discrete data values compared to said second set of discrete data values;
(ii) calculating a plurality of filter function coefficients, based on said scaling factor, utilising at least one of a plurality of filter functions;
(iii) storing said filter function coefficients;
(iv) accessing said stored filter function coefficients; and
(v) performing interpolation on said first set of discrete data values, using said accessed filter function coefficients, to generate said second set of discrete data values.
According to another aspect of the invention there is provided an apparatus for converting a first set of discrete data values to a second set of discrete data values, the apparatus comprising:
calculator means for calculating a scaling factor of said first set of discrete data values compared to said second set of discrete data values, and calculating a plurality of filter function coefficients, based on said scaling factor, utilising at least one of a plurality of filter functions;
storage means for storing said filter function coefficients;
storage access means for accessing said stored filter function coefficients; and
interpolation means for performing interpolation on said first set of discrete data values, using said accessed filter function coefficients, to generate said second set of discrete data values.
According to still another aspect of the invention there is provided a computer readable medium for storing a program for an apparatus which processes data, said processing comprising a method of converting a first set of discrete data values to a second set of discrete data values, said program comprising:
code for calculating a scaling factor of said first set of discrete data values compared to said second set of discrete data values;
code for calculating a plurality of filter function coefficients, based on said scaling factor, utilising at least one of a plurality of filter function;
code for storing said filter function coefficients;
code for accessing said stored filter function coefficients; and
code for performing interpolation on said first set of discrete data values, using said accessed filter function coefficients, to generate said second set of discrete data values.
According to still another aspect of the invention there is provided a method of performing interpolation on a pixel-based image, the method comprising the steps of:
(i) calculating a scaling factor of a first image compared to a second image;
(ii) calculating a plurality of filter function coefficients, based on said scaling factor, utilising one of a plurality of filter functions;
(iii) storing said filter function coefficients;
(iv) detecting incoming pixels of said first image;
(v) accessing said stored filter function coefficients; and
(vi) performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided an apparatus for performing interpolation on a pixel-based image, the apparatus comprising:
calculator means for calculating a scaling factor of a first image compared to a second image, and calculating a plurality of filter function coefficients, based on said scaling factor, utilising one of a plurality of filter functions;
storage means for storing said filter function coefficients;
detection means for detecting incoming pixels of said first image;
coefficient access means for accessing said stored filter function coefficients; and
interpolator for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
In embodiments of the invention, the first image may be a colour image.
According to still another aspect of the invention there is provided a computer readable medium for storing a program for an apparatus which processes data, said processing comprising a method of performing interpolation on a pixel-based image, said program comprising:
code for calculating a scaling factor of a first image compared to a second image, and calculating a plurality of filter function coefficients, based on said scaling factor, utilising one of a plurality of filter functions;
code for storing said filter function coefficients;
code for detecting incoming pixels of said first image;
accessing said stored filter function coefficients; and
code for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided a method of performing interpolation on a pixel-based image, the method comprising the steps of:
(i) inputting dimension values of a first image and a second image:
(ii) calculating a scaling factor of said first image compared to said second image;
(iii) computing interpolation indicators for said second image based on said scaling factor;
(iv) calculating filter function coefficients, according to said interpolation indicators, utilising a filter function, wherein only those filter function coefficients required for said scaling factor are calculated;
(v) storing said filter function coefficients;
(vi) detecting incoming pixels of said first image; and
(vii) accessing said stored filter function coefficients; and
(viii) performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided an apparatus for performing interpolation on a pixel-based image, said apparatus comprising:
input means for inputting dimension values of a first image and a second image:
calculator means for calculating a scaling factor of said first image compared to said second image, computing interpolation indicators for said second image based on said scaling factor, and calculating filter function coefficients, according to said interpolation indicators, utilising a filter function, wherein only those filter function coefficients required for said scaling factor are calculated;
storage means for storing said filter function coefficients;
detection means for detecting incoming pixels of said first image; and
coefficient access means for accessing said stored filter function coefficients; and
interpolator for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided a computer readable medium for storing a program for an apparatus which processes data, said processing comprising a method of performing interpolation on a pixel-based image, said program comprising:
code for inputting dimension values of a first image and a second image:
code for calculating a scaling factor of said first image compared to said second image;
code for computing interpolation indicators for said second image based on said scaling factor;
code for calculating filter function coefficients, according to said interpolation indicators, utilising a filter function, wherein only those filter function coefficients required for said scaling factor are calculated;
code for storing said filter function coefficients;
code for detecting incoming pixels of said first image; and
code for accessing said stored filter function coefficients; and
code for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided a method of performing image interpolation, the method comprising the steps:
(i) inputting dimension values of a first image and a second image;
(ii) calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values;
(iii) computing pairs of interpolation indicators according to said first and second sampling limit values;
(iv) calculating fractional first and second coordinate values using said interpolation indicators;
(v) calculating filter function coefficient values, based on said first and second fractional coordinate values, utilising a filter function;
(vi) storing said filter function coefficient values in a table;
(vii) detecting input pixel values of said first image;
(viii) accessing said stored filter function coefficients; and
(ix) performing image interpolation on said pixels of said first image using said stored filter function coefficient values to produce said second image.
According to still another aspect of the invention there is provided an apparatus for performing image interpolation, the apparatus comprising:
input means for inputting dimension values of a first image and a second image;
calculator means for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values, computing pairs of interpolation indicators according to said first and second sampling limit values, calculating fractional first and second coordinate values using said interpolation indicators, and calculating filter function coefficient values, based on said first and second fractional coordinate values, utilising a filter function;
storage means for storing said filter function coefficient values in a table;
detection means for detecting input pixel values of said first image;
coefficient access means for accessing said stored filter function coefficients; and
interpolator for performing image interpolation on said pixels of said first image using said stored filter function coefficient values to produce said second image.
According to still another aspect of the invention there is provided a computer readable medium for storing a program for an apparatus which processes data, said processing comprising a method of performing image interpolation, said program comprising:
code for inputting dimension values of a first image and a second image;
code for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values;
code for computing pairs of interpolation indicators according to said first and second sampling limit values;
code for calculating fractional first and second coordinate values using said interpolation indicators;
code for calculating filter function coefficient values, based on said first and second fractional coordinate values, utilising a filter function;
code for storing said filter function coefficient values in a table;
detecting input pixel values of said first image;
code for accessing said stored filter function coefficients; and
code for performing image interpolation on said pixels of said first image using said stored filter function coefficient values to produce said second image.
According to still another aspect of the invention there is provided a method of performing interpolation on a first pixel-based image, the method comprising the steps of:
(i) determining dimension values for a second image;
(ii) calculating a plurality of filter function coefficients based on said dimension values;
(iii) storing said filter function coefficients;
(iv) detecting incoming pixels of said first image;
(v) accessing said stored filter function coefficients; and
(vi) performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided an apparatus for performing interpolation on a first pixel-based image, the method comprising the steps of:
calculator means for determining means for determining dimension values for a second image and calculating a plurality of filter function coefficients based on said dimension values;
storage means for storing said filter function coefficients;
detection means for detecting incoming pixels of said first image;
coefficient access means for accessing said stored filter function coefficients; and
interpolator for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided a computer readable medium for storing a program for an apparatus which processes data, said processing comprising a method of performing interpolation on a first pixel-based image, said program comprising:
code for determining dimension values for a second image;
code for calculating a plurality of filter function coefficients based on said dimension values;
code for storing said filter function coefficients;
code for detecting incoming pixels of said first image;
code for accessing said stored filter function coefficients; and
code for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.